package com.xzz.backtrack;

import com.xzz.string.AddStrings;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author: hhz
 * @create: 2022-01-10 14:58
 * 842. 将数组拆分成斐波那契序列
 * 给定一个数字字符串 S，比如 S = "123456579"，我们可以将它分成斐波那契式的序列 [123, 456, 579]。
 *
 * 形式上，斐波那契式序列是一个非负整数列表 F，且满足：
 *
 * 0 <= F[i] <= 2^31 - 1，（也就是说，每个整数都符合 32 位有符号整数类型）；
 * F.length >= 3；
 * 对于所有的0 <= i < F.length - 2，都有 F[i] + F[i+1] = F[i+2] 成立。
 * 另外，请注意，将字符串拆分成小块时，每个块的数字一定不要以零开头，除非这个块是数字 0 本身。
 *
 * 返回从 S 拆分出来的任意一组斐波那契式的序列块，如果不能拆分则返回 []。
 *
 * 输入："123456579"
 * 输出：[123,456,579]
 *
 * 输入: "11235813"
 * 输出: [1,1,2,3,5,8,13]
 **/
public class SplitIntoFibonacci {
    public static void main(String[] args) {
        System.out.println(splitIntoFibonacci("123456579"));
        System.out.println(splitIntoFibonacci("000"));
        System.out.println(splitIntoFibonacci("5511816597"));
        System.out.println(splitIntoFibonacci("26680333094522122405874374286875202793245124106023438638154307674529081118998476463547521258509819378850611547943714168887018710248914570324093142954155261448272417373604331561828074147927642892139798"));

    }
    public static List<Integer> splitIntoFibonacci(String num) {
        List<Integer> res =  new ArrayList<>();
        backtrack(0,num.length(),num,res);
        return res;
    }
    public static boolean backtrack(int start, int end, String num, List<Integer> res) {
        if(start==end){
            int size = res.size();
            return size >= 3 && (res.get(size - 3)+res.get(size - 2))==(res.get(size - 1));
        }
        for (int i = 0; i < num.length(); i++) {
            String curStr = num.substring(0, i + 1);
            if (curStr.length() > 1 && curStr.charAt(0) == '0') {
                continue;
            }
            int curNum = 0;
            try {
                curNum =  Integer.parseInt(curStr);
            }catch (Exception ex){
               continue;
            }
            int size = res.size();
            String nextStr = num.substring(i + 1);
            if (size < 2) {
                res.add(curNum);
            } else {
                if ((res.get(size - 2) + res.get(size - 1)) == curNum) {
                    res.add(curNum);
                } else {
                    continue;
                }
            }
            if(backtrack(start + curStr.length(), end, nextStr, res)){
                return true;
            }
            res.remove(res.size()-1);
        }
        return false;

    }
}
